Packet-based communication systems allow the user of a device, such as a personal computer, to communicate across a computer network such as the Internet.
One type of packet-based communication system uses a peer-to-peer (“P2P”) topology built on proprietary protocols. A P2P network is a mesh of interconnected communications nodes that communicate with each other. In contrast with a classical client-server approach a pure P2P network does not have central servers. Instead, all participating P2P nodes run software that provides various services to other nodes in the network, in addition to giving access to provided services. Such services may include a distributed database service for maintaining information for finding other nodes in the network, or a traffic relaying service to enable connectivity between nodes that cannot communicate directly. Typically, the pure P2P mesh is often accompanied by central servers for certain services, like user authentication or central data storage backup.
One advantage of P2P networks compared to client-server architecture is that of scalability. Participating nodes themselves provide the bandwidth, storage, and CPU resources, so adding more clients also increases the availability of these resources. In pure P2P networks where there are no central servers, there is an additional benefit of not having a single point of failure or performance bottleneck in a system.
In P2P networks that provide direct services to users, each user of the P2P system typically has a unique username which is used to identify the user in the network. It is usual for a user of the P2P system to have a contact list which stores details (including the username) of other users in the P2P system with whom the user communicates. These other users are referred to as the user's “contacts”. The contact list allows the user to initiate a communication event with a contact in a simple manner, for example by clicking on the contact's name in the contact list. The contact list is typically kept on a P2P node, but the operator of the P2P service may also provide a central service for backing up the contact list for purposes of disaster recovery, or synchronization between different P2P nodes that the user uses.
Where the user intends to add a contact to his contact list it can sometimes be difficult for the user to find the username of the intended contact in the P2P system, particularly if the username of the intended contact is different to the intended contact's real name. This may be because the intended contact has willingly chosen a username in the P2P system that is different to their real name. However, in P2P systems such as Skype®, which have a large number of users (for example millions of users), it is highly likely that multiple users will share the same real name. Since usernames in the P2P system are required to be unique, some users will necessarily be forced to have usernames that are different to their real names. Therefore finding intended contacts becomes increasingly difficult as the number of users in the P2P system increases, and the number of users whose usernames are different from their real names correspondingly increases.
In such large systems it is beneficial for the system to use an automated searching facility to search for, and recommend to the user, other users in the system that the user may want to add as contacts to his contact list. It would be beneficial to optimize the automated searching facility in terms of at least one of the speed of the search; the processing resources required; and the relevance of the recommended contacts.
A Friends of Friends search is a known concept which uses the observation that if someone is a mutual friend of your friends then that someone is likely to also be your friend. The terms “friend” and “contact” can be used somewhat interchangeably in the context of the P2P system; in terms of a P2P system such as that described above, someone can be considered a friend of the user if they are a contact of the user. There exists a level of trust between users in the P2P communication system who are contacts (or friends), such that contacts are able to file transfer data between one another over the P2P system and are able to view each other's private details. The Friends of Friends search requires an examination of the contact lists of some or all of a user's friends in order to identify mutual friends of the user's friends. The number of database operations required to implement the Friends of Friends search increases as the number of users in the system increases and as the size of the contact lists increase. In P2P systems, such as Skype®, which have a large number of users (for example millions of users) applying the conventional Friends of Friends search to the central database holding the contact lists for the users requires a large amount of processing power and becomes prohibitively resource-hungry to the extent that it becomes unfeasible to apply the conventional Friends of Friends search to a P2P system having such a large number users.
There is therefore a need for an efficient technique for analysing existing relationships between users of a large P2P system (having for example millions of users) and for performing a search for mutual friends in the contact lists of users who are friends in a large P2P system. Such a technique would provide a feasible method of generating a list of mutual friends of friends in a large P2P system which can be used for recommending new contacts to a user in the P2P system.